package cc.wsyw126.java.nowcoder;

import java.util.Scanner;

/**
 * Created by Administrator on 2017/4/12.
 */
public class LCS {
    public int LCS_LENGTH(String a, String b) throws Exception {
        int result = 0;
        if (a == null || b == null) {
            throw new Exception("null Exception!");
        }
        if (a.length() == 0 | b.length() == 0) {
            return result;
        }
        int raw = a.length(), column = b.length();
        int[][] mark = new int[raw+1][column+1];
        for (int i = 0; i <= raw; i++) {
            mark[i][0] = 0;
        }
        for (int i = 0; i <= column; i++) {
            mark[0][i] = 0;
        }
        for (int i = 0; i < raw; i++) {
            for (int j = 0; j < column; j++) {
                if (a.charAt(i) == b.charAt(j)) {
                    mark[i+1][j+1] = mark[i][j]+1;
                }else {
                    if (mark[i][j+1] >= mark[i+1][j]) {
                        mark[i+1][j+1] = mark[i][j+1];
                    }else {
                        mark[i+1][j+1] = mark[i+1][j];
                    }
                }
            }
        }
        result = mark[raw][column];
        return result;
    }

    public static void main(String[] args) throws Exception {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            String a = scanner.nextLine();
            String b = scanner.nextLine();
            LCS lcs = new LCS();
            int i = lcs.LCS_LENGTH(a, b);
            System.out.println("i = " + i);

        }
    }
}
